package com.aqie.medium.dfs;

import java.util.Stack;

/**
 * 394 字符串解码 todo
 */
public class DecodeString {
    /**
     * 1, 3ms
     * @param s
     * @return
     */
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder(s);

        int index=0;
        int index2=0;
        while((index=sb.indexOf("]"))>=0){
            index2 = sb.lastIndexOf("[",index);
            int numStartIndex=0;
            for(int i=index2-1;i>=0 ;--i){
                if(!Character.isDigit(sb.charAt(i)))  {
                    numStartIndex = i+1;   //确定数字字符串的边界
                    break;
                }
            }
            int num = Integer.parseInt(sb.substring(numStartIndex,index2));
            String temp = sb.substring(index2+1,index);
            StringBuilder temp1= new StringBuilder();
            for(int i=0;i<num;++i){
                temp1.append(temp);
            }
            sb.delete(numStartIndex,index+1);
            sb.replace(numStartIndex,numStartIndex, temp1.toString());
        }
        return sb.toString();
    }

    /**
     * 2, Stack 3ms
     * @param s
     * @return
     */
    public String decodeString2(String s) {
        Stack<String> st = new Stack<>();
        int len = s.length();
        if (len == 0) return s;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) != ']') {
                st.push(s.substring(i, i + 1));
                continue;
            }
            String tmp_res = "";
            while (!st.isEmpty()) {
                if (!st.peek().equals("[")) {
                    tmp_res = st.pop() + tmp_res;
                    continue;
                } else {
                    st.pop();
                    int num = 0;
                    int k = 0;
                    while (!st.isEmpty() && st.peek().length() == 1 && st.peek().charAt(0) >= '0' && st.peek().charAt(0) <= '9') {
                        num += Math.pow(10, k) * Integer.parseInt(st.pop());
                        k++;
                    }
                    String tmp_res2 = "";
                    for (int j = 0; j < num; j++) {
                        tmp_res2 += tmp_res;
                    }
                    st.push(new String(tmp_res2));
                    break;
                }
            }
        }
        String res = "";
        while (!st.isEmpty()) {
            res = st.pop() + res;
        }
        return res;

    }

    /**
     * 3,
     * @param s
     * @return
     */
    public String decodeString3(String s) {
        // todo
        return "";
    }
}
